#define DEBUG
#include <cstdio>

using namespace std;

const int maxn=100000, inf=0x7ffffff;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

class SegmentTree {
public:
  int mark[4*maxn+1], val[4*maxn+1];

  void init(int o, int l, int r) {
    val[o] = inf;
    if (l!=r) {
      int mid=(l+r)/2;
      init(o*2, l, mid);
      init(o*2+1, mid+1, r);
    }
  }

  void markDown(int o, int l, int r) {
    if (mark[o]) {
      val[o] += mark[o];
      if (l!=r) {
	mark[o*2] += mark[o];
	mark[o*2+1] += mark[o];
      }
      mark[o] = 0;
    }
  }

  void set(int o, int l, int r, int t, int v) {
    markDown(o, l, r);
    if (l==r) {
      val[o] = v;
    } else {
      int mid=(l+r)/2;
      if (t<=mid) {
	set(o*2, l, mid, t, v);
      } else {
	set(o*2+1, mid+1, r, t, v);
      }
      markDown(o*2, l, mid);
      markDown(o*2+1, mid+1, r);
      val[o] = min(val[o*2], val[o*2+1]);
    }
  }

  void add(int o, int l, int r, int tl, int tr, int tv) {
    if (l>r) {
      return;
    }
    markDown(o, l, r);
    if (l==tl && r==tr) {
      mark[o] += tv;
      markDown(o, l, r);
    } else {
      int mid=(l+r)/2;
      if (tl<=mid && tr>=l) {
	add(o*2, l, mid, max(tl, l), min(tr, mid), tv);
      }
      if (tl<=r && tr>mid) {
	add(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r), tv);
      }
      markDown(o*2, l, mid);
      markDown(o*2+1, mid+1, r);
      val[o] = min(val[o*2], val[o*2+1]);
    }
  }

  int getMin(int o, int l, int r, int tl, int tr) {
    markDown(o, l, r);
    if (l==tl && r==tr) {
      return val[o];
    } else {
      int mid=(l+r)/2, ret=inf;
      if (tl<=mid && tr>=l) {
	ret = min(ret, getMin(o*2, l, mid, max(tl, l), min(tr, mid)));
      }
      if (tl<=r && tr>mid) {
	ret = min(ret, getMin(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r)));
      }
      return ret;
    }
  }

  int getMinPos(int o, int l, int r, int tl, int tr) {
    markDown(o, l, r);
    if (l==tl && r==tr) {
      return l;
    } else {
      int mid=(l+r)/2;
      if (tl<=mid && tr>mid) {
	markDown(o*2, l, mid), markDown(o*2+1, mid+1, r);
	if (val[o*2]<=val[o*2+1]) {
	  return getMinPos(o*2, l, mid, max(tl, l), min(tr, mid));
	} else {
	  return getMinPos(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r));
	}
      } else if (tl<=mid && tr>=l) {
	return getMinPos(o*2, l, mid, max(tl, l), min(tr, mid));
      } else {
	return getMinPos(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r));
      }
    }
  }
};

class DCTree {
public:
  static const int maxk=19;
  int n, l[4*maxn+1], r[4*maxn+1], minx[4*maxn+1], maxx[4*maxn+1], son[4*maxn+1], bro[4*maxn+1], f[4*maxn+1][maxk+1], map[maxn+1], dep[maxn+1], root;
  bool flag[4*maxn+1];

  void dfs(int o) {
    dep[o] = dep[f[o][0]]+1;
    for (int i=son[o]; i; i=bro[i]) {
      dfs(i);
    }
  }

  void initF() {
    for (int j=1; j<=maxk; j++) {
      for (int i=1; i<=n; i++) {
	f[i][j] = f[f[i][j-1]][j-1];
      }
    }
  }

  void build(int m, int *a) {
    static SegmentTree sgt;
    static int left[maxn+1], stack[maxn+1], quemin[maxn+1][2], quemax[maxn+1][2];
    int mint=1, maxt=1;
    stack[++stack[0]] = ++n;
    quemin[1][0] = quemax[1][0] = l[n] = r[n] = 1;
    quemin[1][1] = quemax[1][1] = minx[n] = maxx[n] = a[1];
    flag[n] = true;
    map[1] = n;
    sgt.init(1, 1, m);
    for (int i=2; i<=m; i++) {
      sgt.add(1, 1, m, 1, i-1, -1);
      for (; mint && quemin[mint][1]>a[i]; mint--) {
	sgt.add(1, 1, m, quemin[mint-1][0]+1, i-1, quemin[mint][1]);
      }
      sgt.add(1, 1, m, quemin[mint][0]+1, i, -a[i]);
      quemin[++mint][0] = i;
      quemin[mint][1] = a[i];
      for (; maxt && quemax[maxt][1]<a[i]; maxt--) {
	sgt.add(1, 1, m, quemax[maxt-1][0]+1, i-1, -quemax[maxt][1]);
      }
      sgt.add(1, 1, m, quemax[maxt][0]+1, i, a[i]);
      quemax[++maxt][0] = i-1;
      quemax[maxt][1] = a[i];

      int top=stack[stack[0]], now=++n;
      if (!sgt.getMin(1, 1, n, 1, i-1)) {
	left[i] = sgt.getMinPos(1, 1, n, 1, i-1);
      } else {
	left[i] = i;
      }
      l[n] = r[n] = 1;
      minx[n] = maxx[n] = a[i];
      flag[n] = true;
      map[i] = n;
      for (; stack[0]; ) {
	if (flag[top] && r[top]-l[top]>0) {
	  if (maxx[now]+1==minx[top] || minx[now]-1==maxx[top]) {
	    minx[top] = min(minx[top], minx[now]), maxx[top] = max(maxx[top], maxx[now]);
	    r[top] = i;
	    f[now][0] = top, bro[now] = son[top], son[top] = now;
	    now = top, top = stack[--stack[0]];
	    continue;
	  }
	}
	if (l[top]==left[i]) {
	  n++;
	  flag[n] = true;
	  l[n] = l[top], r[n] = r[now];
	  minx[n] = min(minx[top], minx[now]), maxx[n] = max(maxx[top], maxx[now]);
	  f[now][0] = n, bro[now] = son[n], son[n] = now;
	  f[top][0] = n, bro[top] = son[n], son[n] = top;
	  now = n, top = stack[stack[0]--];
	  continue;
	}
	bool stop=stack[0]<=1;
	for (int j=stack[0]-1; j>0; j--) {
	  if (l[j]==left[i]) {
	    n++;
	    flag[n] = false;
	    l[n] = l[j], r[n] = r[now];
	    minx[n] = minx[now], maxx[n] = maxx[now];
	    f[now][0] = n, bro[now] = son[n], son[n] = now;
	    now = n;
	    for (; stack[0]>=j; stack[0]--) {
	      top=stack[stack[0]];
	      minx[n] = min(minx[n], minx[top]), maxx[n] = max(maxx[n], maxx[top]);
	      f[top][0] = n, bro[top] = son[n], son[n] = top;
	    }
	    break;
	  } else if (l[j]<left[i] && left[i]<=r[j]) {
	    n++;
	    flag[n] = false;
	    l[n] = l[j+1], r[n] = r[now];
	    minx[n] = minx[now], maxx[n] = maxx[now];
	    f[now][0] = n, bro[now] = son[n], son[n] = now;
	    now = n;
	    for (; stack[0]>j; stack[0]--) {
	      top=stack[stack[0]];
	      minx[n] = min(minx[n], minx[top]), maxx[n] = max(maxx[n], maxx[top]);
	      f[top][0] = n, bro[top] = son[n], son[n] = top;
	    }
	    break;
	  } else if (l[j]>left[i] || j<=1) {
	    stop = true;
	    break;
	  }
	}
	if (stop) {
	  break;
	}
      }
      stack[++stack[0]] = now;
    }
    root=stack[stack[0]];
    dfs(root);
    initF();
  }

  int lca(int u, int v)  {
    if (dep[u]<dep[v]) {
      int temp;
      temp = u, u = v, v = temp;
    }
    for (int i=maxk; i>=0; i--) {
      if (dep[f[u][i]]>=dep[v]) {
	u = f[u][i];
      }
    }
    if (u==v) {
      return u;
    }
    for (int i=maxk; i>=0; i--) {
      if (f[u][i]!=f[v][i]) {
	u = f[u][i], v = f[v][i];
      }
    }
    return f[u][0];
  }

  void getAns(int tl, int tr, int &ansl, int &ansr) {
    int t = lca(map[tl], map[tr]);
    ansl = l[t], ansr = r[t];
    if (flag[t]) {
      for (int i=son[t]; i; i=bro[i]) {
	if (l[i]<=tl && l[i]>=ansl) {
	  ansl = l[i];
	}
	if (r[i]>=tr && r[i]<=ansr) {
	  ansr = r[i];
	}
      }
    }
  }
};

int main() {
  freopen("sequence.in", "r", stdin);
  freopen("sequence.out", "w", stdout);

  static DCTree dctree;
  static int cow[maxn+1];
  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    scanf("%d", cow+i);
  }

  dctree.build(n, cow);

  int m;
  scanf("%d", &m);
  for (int i=1; i<=m; i++) {
    int l, r, ansl, ansr;
    scanf("%d %d", &l, &r);
    dctree.getAns(l, r, ansl, ansr);
    printf("%d %d\n", ansl, ansr);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
